Sunghee Yun (He/Him)

Co-founder & CTO @ Erudio Bio, Inc., Chief Business Development Officer @ WeStory.ai, Advisor & Evangelist @ CryptoLab, Inc., KFAS-Salzburg Global Leadership Initiative Fellow @ Salzburg Global Seminar, Adjunct Professor @ Sogang University, Advisory Professor @ DGIST, Global Advisory Board Member @ Innovative Future Brain-Inspired Intelligence System Semiconductor of Sogang University, Network Expert @ Gerson Lehrman Group

Abstract

This seminar provides a comprehensive introduction to convex optimization and dual problems, exploring their fundamental importance in machine learning and engineering applications. The presentation begins by establishing why convex optimization deserves special attention in the landscape of mathematical optimization: many machine learning algorithms inherently depend on convex optimization, and unlike general optimization problems which are often intractable, convex optimization problems can actually be solved reliably and efficiently.

The mathematical foundation of optimization problems is presented in standard form, where we minimize an objective function subject to inequality and equality constraints. The seminar demonstrates how machine learning naturally fits this framework, with model parameters (such as neural network weights) serving as optimization variables, loss functions as objectives, and network architectures defining constraints. This connection illustrates the pervasive role of optimization in modern AI systems.

A key insight presented is the stark contrast between convex and non-convex optimization difficulty. While a generalized geometric program with 3,000 variables and 1,000 constraints can be solved to global optimality within one minute on a laptop, a seemingly simpler 10th-order polynomial minimization problem with just 20 variables and no constraints remains practically unsolvable. This paradox highlights the special mathematical structure that makes convex problems tractable.

The seminar explores several classes of convex optimization problems that admit efficient solutions. Least-squares problems, which have been studied since Gauss, possess analytic solutions and extremely reliable algorithms. Linear programming, systematically developed since World War II, uses methods like the simplex algorithm and interior-point methods. More recent developments include semidefinite programming and maximum determinant problems, which extend the reach of convex optimization to previously intractable domains.

Machine learning applications of convex optimization are illustrated through several canonical examples. Linear regression reduces to a least-squares problem with a closed-form solution obtained by setting the gradient to zero. Ridge regression adds L2 regularization to prevent overfitting while maintaining the convex structure and solvability. Lasso regression incorporates L1 regularization for parameter selection, requiring reformulation with additional variables to handle the non-smooth objective function.

Support Vector Machines (SVM) provide a sophisticated example of convex optimization in classification problems. The SVM formulation seeks a hyperplane that separates classes with maximum margin, leading to a quadratic programming problem with linear constraints. The inclusion of slack variables allows for soft margins, while kernel methods enable non-linear decision boundaries through feature space transformations, all while preserving the convex optimization structure.

The concept of duality represents a fundamental principle in optimization theory: every constrained optimization problem, regardless of whether it is convex, has an associated dual problem that is always convex. This duality relationship provides powerful theoretical insights and practical computational advantages. The dual problem often reveals hidden structure in the original problem and can be easier to solve than the primal formulation.

Lagrangian duality forms the mathematical foundation for dual problems. The Lagrangian function incorporates constraints into the objective using multiplier variables, and the dual function is defined as the infimum of the Lagrangian over the primal variables. A crucial property is that the dual function always provides a lower bound on the optimal value of the primal problem, known as weak duality. Under certain conditions, this bound is tight, achieving strong duality where the primal and dual optimal values are equal.

The Karush-Kuhn-Tucker (KKT) conditions provide necessary and sufficient optimality conditions for convex optimization problems when strong duality holds. These conditions encompass primal and dual feasibility, complementary slackness (which requires that either a constraint is active or its multiplier is zero), and the requirement that the gradient of the Lagrangian vanishes. For convex problems satisfying constraint qualifications like Slater’s condition, the KKT conditions completely characterize optimality.

The SVM dual problem exemplifies the power of duality in machine learning. The dual formulation transforms the original quadratic program into one involving only the training data through inner products, enabling the kernel trick for non-linear classification. The KKT conditions reveal that only support vectors (data points with non-zero multipliers) affect the decision boundary, providing both computational efficiency and interpretability. This sparse representation is fundamental to SVM’s effectiveness and scalability.

The seminar concludes by highlighting the broader implications of convex optimization and duality theory. These mathematical frameworks provide not only computational tools for solving optimization problems but also theoretical insights into the structure of learning algorithms. The dual variables often have meaningful interpretations (such as sensitivity analysis), and duality gaps provide optimality certificates during iterative algorithms. Future discussions could explore advanced algorithms, convergence analysis, and applications in approximation, statistical estimation, and geometric problems, demonstrating the continuing relevance of these foundational mathematical concepts in modern machine learning and engineering.